1. Field of the Invention
This invention relates to network routing.
2. Related Art
In routing packets in a network, a router sometimes has a choice of more than one path to a selected destination. When there is more than one path, there is a possibility that the router can distribute packet traffic among the paths, so as to reduce the aggregate packet traffic load on any one individual path. This concept is known in the art of network routing as xe2x80x9cload sharing.xe2x80x9d
One problem that has arisen in the art is that sharing packet traffic among more than one such path can result in out-of-order arrival of packets at the destination device (or at an intermediate device on both paths to the destination device). Out-of-order arrival of packets is generally undesirable, as some protocols rely on packets arriving in the order they were sent.
Accordingly, it would be desirable to share packet traffic load among more than one such path, while maintaining the order in which the packets were sent in all cases where order matters. The invention provides load-sharing that is preferably performed on a per-flow basis, but possibly on a per-packet basis. A xe2x80x9cflowxe2x80x9d is a sequence of packets transmitted between a selected source and a selected destination, generally representing a single session using a known protocol. Each packet in a flow is expected to have identical routing and access control characteristics.
Flows are further described in detail in the following patent applications:
U.S. Application Ser. No. 08/581,134, titled xe2x80x9cMethod For Traffic Management, Traffic Prioritization, Access Control, and Packet Forwarding in a Datagram Computer Networkxe2x80x9d, filed Dec. 29, 1995, in the name of inventors David R. Cheriton and Andreas V. Bechtolsheim, assigned to Cisco Technology, Inc;.
U.S. Application Ser. No. 08/655,429, titled xe2x80x9cNetwork Flow Switching and Flow Data Exportxe2x80x9d, filed May 28, 1996, in the name of inventors Darren Kerr and Barry Bruins, and assigned to Cisco Technology, Inc.; and
U.S. Application Ser. No. 08/771,438, titled xe2x80x9cNetwork Flow Switching and Flow Data Exportxe2x80x9d, filed Dec. 20, 1996, in the name of inventors Darren Kerr and Barry Bruins, assigned to Cisco Technology, Inc.,
PCT International Application PCT/US 96/20205, titled xe2x80x9cMethod For Traffic Management, Traffic Prioritization, Access Control, and Packet Forwarding in a Datagram Computer Networkxe2x80x9d, filed Dec. 18, 1996, in the name of inventors David R. Cheriton and Andreas V. Bechtolsheim, and assigned to Cisco Technology, Inc;, and
Ser. No. 08/0655,429 Express Mail Mailing No. EM053698725US, titled xe2x80x9cNetwork Flow Switching and Flow Data Exportxe2x80x9d, filed Jul. 2, 1997, in the name of inventors Darren Kerr and Barry Bruins, assigned to Cisco Technology, Inc.
These patent applications are collectively referred to herein as the xe2x80x9cNetflow Switching Disclosures.xe2x80x9d Each of these applications is hereby incorporated by reference as if fully set forth herein.
However, one problem with sharing packet traffic load among more than one such path, whether on a per-packet basis or on a per-flow basis, is that the number of packets or the number of flows may not be evenly divisible by the number of such paths. In fact, with the number of packets or the number of flows continually changing, it would be difficult at best to maintain an even distribution of packets or flows into the number of such paths.
One response to this problem is to provide a hash function, to pseudo-randomly assign each packet or each flow to a hash value, and to share the packet traffic load among the paths in response to the hash value (such as by associating each hash table entry with a selected path). While this technique achieves the purpose of sharing the packet traffic load among more than one path to the destination, it has the drawback that packet traffic load is typically not evenly divided, particularly when the number of such paths is not a power of two.
For example, if there are three bits of hash value, thus providing eight possible hash values in all, but there are only five paths to the destination (or the weighted sum of desirable path loads is a multiple of five), the first five hash values would be evenly distributed among the paths, but the remaining three hash values would be unevenly distributed to three of the five possible paths.
One response to this problem is to select a hash value with more bits, and thus with more possible values, so as to more evenly distribute packets or flows among the possible paths. While this method achieves the purpose of evenly distributing packet traffic load, it has the drawback of requiring a relatively large amount of memory for the associated hash table, an amount of memory which is relatively larger as the amount of desired load imbalance is reduced.
Accordingly, it would be advantageous to provide a method and system in which packet traffic can be relatively evenly divided among a plurality of possible paths, without requiring a relatively large amount of memory. This advantage is achieved in an embodiment of the invention which provides a hash value with a relatively large number of bits, but which provides for processing that hash value using the number of possible paths so as to associate that hash value with a selected path using a table having a relatively small number of entries. The processing can be performed rapidly in hardware using a relatively small amount of circuitry.
The invention provides a method and system for sharing packet traffic load among a plurality of possible paths. Each packet is associated with a flow, and a hash value is determined for each flow, so as to distribute the sequence of packets into a set of hash buckets. The hash value has a relatively large number of bits, but is divided by the number of possible paths so as to achieve a relatively small modulus value; the modulus value is used to index into a relatively small table associating one selected path with each entry.
In a preferred embodiment, the modulus value is determined by a relatively small amount of circuitry, simultaneously for a plurality of modulii, and one such modulus value is selected in response to the number of possible paths.